package com.mango.algorithm.tree.binary;

import com.mango.data.structure.binarytree.linknode.TreeNode;

import java.util.*;

class Test{
    public static TreeNode init(){
        // 构建如下的二叉树
        //           1
        //     2          3
        //  4    5     6     7
        TreeNode head = new TreeNode(1);
        TreeNode v2 = new TreeNode(2);
        TreeNode v3 = new TreeNode(3);
        TreeNode v4 = new TreeNode(4);
        TreeNode v5 = new TreeNode(5);
        TreeNode v6 = new TreeNode(6);
        TreeNode v7 = new TreeNode(7);

        head.left = v2;
        head.right = v3;
        v2.left = v4;
        v2.right = v5;
        v3.left = v6;
        v3.right = v7;
        return head;
    }
    public static void main(String[] args) {
        TreeNode head = init();
        System.out.println("递归序:");
        recursion(head);
        System.out.println();
        System.out.println("前序遍历:");
        preOver(head);
        System.out.println();
        System.out.println("中序遍历:");
        inOver(head);
        System.out.println();
        System.out.println("后序遍历:");
        backOver(head);
        System.out.println();
        System.out.println("前序遍历:(非递归)");
        pre(head);
        System.out.println();
        System.out.println("中序遍历:(非递归)");
        in(head);
        System.out.println();
        System.out.println("中序遍历:(非递归)");
        back(head);
        System.out.println();
        System.out.println("宽度优先遍历：(wfs)");
        wfs(head);
        System.out.println();
        System.out.println("打印二叉树：");
        printTree(head);

    }
    // 递归序，每个节点到3次
    public static void recursion(TreeNode node){
        if(node == null){
            return ;
        }
        System.out.print(node.val+"->");
        recursion(node.left);
        System.out.print(node.val+"->");
        recursion(node.right);
        System.out.print(node.val+"->");
    }
    // 前序遍历，头左右
    public static void preOver(TreeNode node){
        if(node == null){
            return ;
        }
        // 在第一次处理
        System.out.print(node.val+"->");
        preOver(node.left);
        preOver(node.right);
    }
    // 中序遍历，左头右
    public static void inOver(TreeNode node){
        if(node == null){
            return ;
        }
        inOver(node.left);
        // 在第二次处理
        System.out.print(node.val+"->");
        inOver(node.right);
    }
    // 后序遍历，左右头
    public static void backOver(TreeNode node){
        if(node == null){
            return ;
        }
        backOver(node.left);
        backOver(node.right);
        // 在第三次处理
        System.out.print(node.val+"->");
    }
    // 前序遍历，非递归
    public static void pre(TreeNode node){
        Stack<TreeNode> stack = new Stack<>();
        // 头节点入栈
        stack.push(node);
        while(!stack.isEmpty()){
            TreeNode cur = stack.pop();
            System.out.print(cur.val+"->");
            // 先压右，再压左
            if(null != cur.right){
                stack.push(cur.right);
            }
            if(null != cur.left){
                stack.push(cur.left);
            }
        }
    }
    // 中序遍历，非递归
    public static void in(TreeNode node){
        Stack<TreeNode> stack = new Stack<>();
        // 头节点入栈
        stack.push(node);
        while(!stack.isEmpty()){
            // 左子数入栈
            while(node.left != null){
                stack.push(node.left);
                node = node.left;
            }
            TreeNode cur = stack.pop();
            System.out.print(cur.val+"->");
            // 如果有右，则右节点入栈
            if(null != cur.right){
                stack.push(cur.right);
                // 将node指针指向右节点
                node = cur.right;
            }
        }
    }
    // 后序遍历，非递归
    public static void back(TreeNode node){
        Stack<TreeNode> stack = new Stack<>();
        Stack<TreeNode> collect = new Stack<>();
        // 头节点入栈
        stack.push(node);
        while(!stack.isEmpty()){
            TreeNode cur = stack.pop();
            // 弹出的元素放到收集栈内
            collect.push(cur);
            // 先压左再压右
            if(null != cur.left){
                stack.push(cur.left);
            }
            if(null != cur.right){
                stack.push(cur.right);
            }
        }
        // 最后弹出收集栈里的节点
        while(!collect.isEmpty()){
            System.out.print(collect.pop().val+"->");
        }
    }
    // 宽度优先遍历
    public static void wfs(TreeNode node){
        // 基于队列实现
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(node);
        while(!queue.isEmpty()){
            TreeNode cur = queue.poll();
            System.out.print(cur.val+"->");
            if(cur.left != null){
                queue.offer(cur.left);
            }
            if(cur.right != null){
                queue.offer(cur.right);
            }
        }
    }
    // 获取中序遍历list
    public static List<TreeNode> getInList(TreeNode node){
        List<TreeNode> result = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        // 头节点入栈
        stack.push(node);
        while(!stack.isEmpty()){
            // 左子数入栈
            while(node.left != null){
                stack.push(node.left);
                node = node.left;
            }
            TreeNode cur = stack.pop();
            result.add(cur);
            // 如果有右，则右节点入栈
            if(null != cur.right){
                stack.push(cur.right);
                // 将node指针指向右节点
                node = cur.right;
            }
        }
        return result;
    }
    // 得到节点层级hash表和高度level
    public static int handleTreeLevel(Map<TreeNode,Integer> levelMap,TreeNode node){
        int level = 1;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(node);
        levelMap.put(node,level);
        while(!queue.isEmpty()){
            TreeNode cur = queue.poll();
            // 不等于当前level，说明level到了下一层，则level+1
            if(levelMap.get(cur) != level){
                level++;
            }
            levelMap.put(cur,level);
            if(cur.left != null){
                queue.offer(cur.left);
                levelMap.put(cur.left,level+1);
            }
            if(cur.right != null){
                queue.offer(cur.right);
                levelMap.put(cur.right,level+1);
            }
        }
        return level;
    }

    public static int handleTreeLevel2(Map<TreeNode,Integer> levelMap,TreeNode node){
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(node);
        int level = 1;
        while(!queue.isEmpty()){
            int size = queue.size();
            while (size>0) {
                TreeNode cur = queue.poll();
                if (cur.left != null) {
                    queue.offer(cur.left);
                }
                if (cur.right != null) {
                    queue.offer(cur.right);
                }
                levelMap.put(cur,level);
                size--;
            }
            level++;
        }
        return level;
    }
    // 层序遍历
    public List<List<Integer>> levelOrder(TreeNode root) {
        if(root == null){
            return new ArrayList();
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        List<List<Integer>> result = new ArrayList();
        while(!queue.isEmpty()){
            int size = queue.size();
            List<Integer> list = new ArrayList();
            while (size>0) {
                TreeNode cur = queue.poll();
                if (cur.left != null) {
                    queue.offer(cur.left);
                }
                if (cur.right != null) {
                    queue.offer(cur.right);
                }
                list.add(cur.val);
                size--;
            }
            result.add(list);
        }
        return result;
    }

    // 打印二叉树，基于中序遍历顺序加节点层级构建二维数组实现打印
    public static void printTree(TreeNode node){
        List<TreeNode> inList = getInList(node);
        Map<TreeNode,Integer> levelMap = new HashMap<>();
        int level = handleTreeLevel2(levelMap,node);
        // 以中序遍历顺序构建二维数组
        int row = level;
        int col = (int) Math.pow(2,row)-1;
        int[][] nums = new int[row][col];
        for(int i=0;i<inList.size();i++){
            TreeNode cur = inList.get(i);
            nums[levelMap.get(cur)-1][i] = cur.val;
        }
        // 打印二维数组
        for(int i=0;i<row;i++){
            for(int j=0;j<col;j++){
                System.out.print(0 == nums[i][j] ? "\t": getPre0Str(nums[i][j]));
            }
            System.out.println();
        }
    }
    // 获取4位补空格的字符串
    public static String getPre0Str(int num){
        String str = num+"";
        int count = 4 - str.length();
        while (count>0){
            str = " "+str;
            count--;
        }
        return str;
    }
}